1. Field of the Invention
The present invention relates to number generators, and in particular to number generators for generating a pseudorandom sequence of numbers.
2. Description of Related Art
Such a well-known random number generator is illustrated in FIG. 5. The pseudorandom number generator of FIG. 5, which is also referred to as a linear feedback shift register, includes a plurality of memory elements 51, 52, 53, 54, which in FIG. 5 are numbered from 0 to n. The memory cells can be initialized to a starting value via initializing means 55. The memory cells 51 to 54, as a whole, form feedforward means, while the linear shift register formed by the memory cells 51 to 54 is fed back by feedback means coupled between an output 56 of the circuit and the memory cell n. In detail, the feedback means includes one or several combining means 54, 58 fed by respective feedback branches 59a, 59b, 59c, as is exemplarily illustrated in FIG. 5. The output value of the last combining means 58 is fed into the memory cell n indicated by 54 in FIG. 5.
The linear feedback shift register shown in FIG. 5 is operated by a clock such that the occupancy of the memory cells, referring to FIG. 5, is shifted by one step to the left in each clock cycle so that the state stored in the memory means 51 is output as a number in each clock cycle, while at the same time the value at the output of the last combining means 58 is fed into the first memory unit n of the sequence of memory units. The linear feedback register illustrated in FIG. 5 thus provides a sequence of numbers responsive to a sequence of clock cycles. The sequence of numbers obtained at the output 56 depends on the starting state set up by the initializing means 55 before starting the shift register. The starting value input by the initializing means 55 is also referred to as a seed, which is why such arrangements illustrated in FIG. 5 are also referred to as seed generators.
The sequence of numbers obtained at the output 56 is referred to as a pseudorandom sequence of numbers, since the numbers seem to follow one another in a random way, but, as a whole, are periodic even though the period duration is large. In addition, the sequence of numbers can be repeated uniquely and thus has a pseudorandom nature if the initializing value fed to the memory elements by the initializing means 54 is known. Such shift registers are, for example, employed as key stream generators to provide a stream of encrypting/decrypting keys depending on a special initializing value (seed).
Such shift registers illustrated in FIG. 5 have the disadvantage of a small linear complexity. Thus, 2 n bits of the output sequence suffice in an n bit LFSR (linear feedback shift register) to calculate the entire sequence. The advantage of such well-known LFSRs illustrated in FIG. 5, however, is that the hardware expenditure is very small.
In addition, there are irregularly clocked LFSRs. They have a somewhat increased hardware expenditure with an almost always lower period. The linear complexity can, however, be considerably higher. A disadvantage of such irregularly clocked devices, however, is the fact that, due to the irregular clocking, the output sequence could be deducted in principle by current measurements in an SPA (simple power analysis). By employing shift register devices as parts of key generators which generate data to be kept secret inherently, that is key data, it is of especial importance that they be protected from any kind of cryptographic attack.
On the other hand, there is the requirement for such devices, in particular when they are to be accommodated on chip cards, that the hardware expenditure be small. Put differently, the chip area such devices occupy needs to be as small as possible. This is due to the fact that, in semiconductor manufacturing, the chip area of an entire device in the end determines the price and thus the profit margin of the chip manufacturer. In addition, especially in chip cards, a specification is usually such that a customer says that a processor chip can have a maximum area in square millimeters, on which most various functionalities must be accommodated. Thus, it is up to the circuit manufacturer to distribute this precious area to the individual components. As regards cryptographic algorithms, which are becoming increasingly complex, efforts of the chip manufacturer are directed to the chip having as much memory as possible to be able to calculate even operating memory-intense algorithms in an acceptable time. The chip area for key generators and other such components thus needs to be kept as small as possible to be able to accommodate more memory on a given chip area.
The general requirement to key generators and devices for generating a pseudorandom sequence of numbers, respectively, thus is, on the one hand, to be safe and, on the other hand, to require as little space as possible, that is to have the smallest hardware expenditure possible.
In principle, linear shift registers have different applications in coding theory, cryptography and other electro-technological areas. The output sequences of linear shift registers comprise useful structural characteristics which can be divided into algebraic characteristics and distribution characteristics.
It is well-known that an output sequence of an n step linear shift register, as has been explained, is periodic. The length of the period can be quite large and is, with regard to n, that is the number of memory elements, often exponential. The length of the period, in particular, is 2n−1, when the shift register is based on a primitive feedback polynomial.
The linear complexity of such a sequence, however, is at most n. The linear complexity of a periodic sequence, according to the definition, equals the number of cells of the smallest possible shift register which can generate the sequence considered.
Due to this fact, it can be shown that, as has been discussed, 2 n subsequent expressions of the sequence suffice to predict all the remaining expressions of the sequence. In addition, there is an efficient algorithm, the so-called Berlekamp-Massey algorithm, to calculate the parameters required to obtain the entire sequence. Thus, sequences of linear shift registers, despite their potentially large periods and their statistically good distributing characteristics, are not suitable directly as key sequences in so-called current ciphers. In addition, there are other applications in which the comparably low linear complexity of a sequence generated by a linear shift register must be seen as a disadvantage.
Usually, linear shift registers are described by their characteristic polynomial. The degree of the characteristic polynomial equals the number of delay elements, usually embodied as flip-flops, of the shift register considered. The exponents of the terms of f(x), except for the leading term, correspond to the shift elements of the shift register contributing to a feedback. The linear shift register illustrated in FIG. 5 would thus have a characteristic polynomial of the following kind:F(x)=xn+1+xn+ . . . +x+1
If such linear shift registers, as are exemplarily illustrated in FIG. 5, are loaded with an initializing state by the initializing means 55, wherein this state is also referred to as a starting state vector, they will typically output a periodic sequence having a certain pre-period and a subsequent period, depending on the implementation. Linear shift registers are always periodic. In technological applications, it is often strived for that the output sequence have both a large period length and a high linear complexity.